277C - Game - CodeForces Solution

#include<iostream>
#include<algorithm>

using namespace std;

struct CutSegment {
	int k, l, r;
} cuts[220000];

int ans;

CutSegment make(int k, int l, int r) {
	if (l > r)
		swap(l, r);

	CutSegment res = {k, l, r};

	return res;
}

bool cmp(const CutSegment &a, const CutSegment &b) {
	return a.k < b.k || a.k == b.k && a.l < b.l;
}

void answer(int dir, int k, int l, int r) {
	if (dir == 0)
		cout << k << " " << l << " " << k << " " << r << endl;
	else 
		cout << l << " " << k << " " << r << " " << k << endl;
	exit(0);
}

void work(int dir, int l, int r, int N, int M, int fl) {
	int j, currR, res;
	int num = 0;
	int optimalMove = 0;

	if (N && (l > r || cuts[l].k != 1))
		optimalMove = 1;
	 
    for (int i = l; i <= r; i = j) {
		res = 0;
		currR = 0;
		for (j = i; cuts[j].k == cuts[i].k; ++j) {
			if (cuts[j].l > currR) {
				res += cuts[j].l - currR;
				currR = cuts[j].r;
			} else {
				currR = max(currR, cuts[j].r);
			}
		}
        
        res += M - currR;

        if (fl) {
			if (res >= (res^ans)) {
				int need = res - (res^ans);
				currR = 0;

				for (int k = i; k < j; ++k) {
					if (cuts[k].l > currR) {
						if (cuts[k].l - currR < need) {
							need -= cuts[k].l - currR;
						} else {
							answer(dir, cuts[k].k, 0, currR + need);
						}
						currR = cuts[k].r;
					} else {
						currR = max(currR, cuts[k].r);
					}
				}
				answer(dir, cuts[i].k, 0, currR + need);
			}
		} else {
			ans ^= res;
		}
		num++;

		if (cuts[i].k != N && cuts[i].k + 1 != cuts[j].k)
			optimalMove = cuts[i].k + 1;
    }

    if (!fl) {
		if ((N - num) & 1)
			ans ^= M;
	} else {
		if(optimalMove && M >= (M^ans))
			answer(dir, optimalMove, 0, M - (M^ans));
	}
}

int main() {
    int n, m, k;
	cin >> n >> m >> k;

	int tot1 = 0; 
	int tot2 = k;

	for (int i = 1; i <= k; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2)
			cuts[++tot1] = make(x1, y1, y2);
		else 
			cuts[++tot2] = make(y1, x1, x2);
	}

    sort(cuts + 1, cuts + tot1 + 1, cmp);
	sort(cuts + k + 1, cuts + tot2 + 1, cmp);
	work(0, 1, tot1, n - 1, m, 0);
	work(1, k + 1, tot2, m - 1, n, 0);

    if(ans) {
		cout << "FIRST" << endl;
		work(0, 1, tot1, n - 1, m, 1);
		work(1, k + 1, tot2, m - 1, n, 1);
	} else {
		cout << "SECOND" << endl;
	}

    return 0;
}/*1693390724.3280349*/